#include <stdio.h>

#define LEN     512
#define MAX_R   5
#define MAX_C   5

struct point {
    int r;
    int c;
    int predecessor;
}queue[LEN];
int head = 0, tail = 0;

static inline int is_empty(void)
{
    return (head == tail);
}

static inline void enqueue(struct point p)
{
    queue[tail++] = p;
}

static inline struct point dequeue(void)
{
    return queue[head++];
}

int maze[MAX_R][MAX_C] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};

void print_maze(void)
{
    int i, j;
    for (i = 0; i < MAX_R; i++) {
        for (j = 0; j < MAX_C; j++)
            printf("%d ", maze[i][j]);
        putchar('\n');
    }
    printf("*********\n");
}

void visit(int r, int c, struct point pre)
{
    struct point visit_point = {r, c, head-1};
    maze[r][c] = 8;
    enqueue(visit_point);
}

int main(void)
{
    struct point p = {0, 0, -1};

    maze[p.r][p.c] = 8;
    enqueue(p);

    while (!is_empty()) {
        p = dequeue();
        if (p.r == MAX_R - 1 && p.c == MAX_C - 1)       /* goal */
            break;
        if (p.c+1 < MAX_C && maze[p.r][p.c+1] == 0)     /* right */
            visit(p.r, p.c+1, p);
        if (p.r+1 < MAX_R && maze[p.r+1][p.c] == 0)     /* down */
            visit(p.r+1, p.c, p);
        if (p.c-1 >= 0 && maze[p.r][p.c-1] == 0)        /* left */
            visit(p.r, p.c-1, p);
        if (p.r-1 >= 0 && maze[p.r-1][p.c] == 0)        /* up */
            visit(p.r-1, p.c, p);
        print_maze();
    }
    if (p.r == MAX_R - 1 && p.c == MAX_C - 1) {
        printf("(%d, %d)\n", p.r, p.c);
        while (p.predecessor != -1) {
            p = queue[p.predecessor];
            printf("(%d, %d)\n", p.r, p.c);
        }
    } else
        printf("No path!\n");
    return 0;
}

